/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 刘柄华
 * Date: 2022-05-22
 * Time: 19:57
 */
public class TestDemo04 {
    /*
    * 重建二叉树  给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
    * 递归
    * */

    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        if(pre.length==0||pre.length==0){
            return null;
        }
        return reConstructBinaryTreeHelper(pre,0,pre.length-1,vin,0,vin.length-1);
    }
    public TreeNode reConstructBinaryTreeHelper(int[] pre,int ps,int pe,int[] vin,int vs,int ve){
        if(ps>pe || vs>ve){
            return null;
        }
        TreeNode root = new TreeNode(pre[ps]);
        for(int i=vs; i<=ve;i++){
            if(vin[i]==pre[ps]){
                root.left = reConstructBinaryTreeHelper(pre,ps+1,ps+i-vs,vin,vs,i-1);
                root.right = reConstructBinaryTreeHelper(pre,ps+i-vs+1,pe,vin,i+1,ve);
                break;
            }
        }
        return root;
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
}
